Heap binomial

Em ciência da computação, um heap binomial é um tipo de heap semelhante a um heap binário, mas que também suporta a rápida união entre duas heaps. Isso é conseguido através do uso de uma estrutura de árvore especial. Ela é importante como uma implementação da mergeable heap (tipo abstrato de dado), que é uma fila de prioridade que suporta a operação de merge.

Heap binomial

Um heap binomial é implementado como uma coleção de árvores binomiais (compare com um heap binário, que tem a forma de uma única árvore binária), que são definidos recursivamente da seguinte forma:

Uma árvore binomial de ordem 0 é um único nó
Uma árvore binomial de ordem k tem um nó raiz cujos filhos são raízes de árvores binomiais de ordens k-1, k-2, ..., 2, 1, 0 (nesta ordem).

Uma árvore binomial de ordem k tem 2^k nós, e altura k.

Devido a sua estrutura singular, uma árvore binomial de ordem k pode ser construída a partir de duas árvores de ordem k-1 trivialmente, anexando uma delas como filho mais à esquerda da raiz da outra árvore. Este recurso é fundamental para a operação de merge em um heap binomial, que é a sua maior vantagem sobre as outras heaps convencionais.

O nome vem da forma: uma árvore binomial de ordem $n$ tem ${\tbinom {n}{d}}$ nós em profundidade $d$ . (Ver coeficiente binomial.)

Estrutura de um heap binomial

Um heap binomial é implementado como um conjunto de árvores binomiais que satisfazem as propriedades do heap binomial:

Cada árvore binomial em um heap obedece à propriedade do min-heap: a chave de um nó é maior que ou igual a chave de seu pai.
Só pode haver uma ou zero árvores binomiais para cada ordem, inclusive a ordem zero.

A primeira propriedade garante que a raiz de cada árvore binomial contém a menor chave na árvore, que se aplica a todo o heap.

A segunda propriedade implica que um heap binomial com n nós consiste em no máximo log n + 1 árvores binomiais. Na verdade, os números e ordens destas árvores são exclusivamente determinados pelo número de nós n: cada árvore binomial corresponde a um dígito na representação binária de número n. Por exemplo, o número 13 é 1101 em binário, $2^{3}+2^{2}+2^{0}$ e, assim, um heap binomial com 13 nós será composto de três árvores binomiais de ordens 3, 2, e 0 (ver figura abaixo).

Exemplo de um heap binomial contendo 13 nós com chaves diferentes.

A heap consiste de três árvores binomiais com ordens de 0, 2, e 3.

Implementação

Devido ao fato que nenhuma operação que requer acesso aleatório para os nós raiz da árvore binomial, as raízes das árvores binomiais podem ser armazenados em uma lista ligada, ordenados pela ordem da árvore de forma crescente.

Merge

Como mencionado acima, a mais simples e mais importante operação é a fusão de duas árvores binomiais de mesma ordem dentro de um heap binomial. Devido à estrutura das árvores binomiais, eles podem ser mescladas trivialmente. Como o nó raiz é o menor elemento da árvore, comparando-se as duas chaves, o menor deles é a chave mínima, que se torna o novo nó raiz. Em seguida, a outra árvore torna-se uma subárvore da árvore mesclada. Esta operação é básica para a completa fusão entre dois heaps binomiais.

função mergeArvore(p, q)
 se p.raiz.chave <= q.raiz.chave
     retorne p.addSubArvore(q)
 senão
     retorne p.addSubArvore(p)

A operação de fusão de duas heaps é, talvez, a mais interessante e pode ser usada como uma sub-rotina na maioria das outras operações. As listas de raízes de ambas as heaps são percorridas simultaneamente de uma maneira semelhante ao algoritmo de merge.

Se apenas um dos heaps contém uma árvore de ordem j, esta árvore é movida para o heap mesclado. Se ambas as heaps contêm uma árvore de ordem j, as duas árvores são mescladas para uma árvore de ordem j+1, de modo que a propriedade de min-heap é satisfeita. Note que pode ser necessário mais tarde mesclar esta árvore com outra árvore de ordem j+1 presente em uma das heaps. No decorrer do algoritmo, precisamos examinar mais de três árvores de qualquer ordem (duas de dois heaps mesclados e outro composto de duas pequenas árvores).

Porque cada árvore binomial em um heap binomial corresponde a um bit na representação binária do seu tamanho, há uma analogia entre a fusão de duas heaps e a adição binária dos tamanhos das duas heaps, a partir da direita-para-esquerda. Sempre que um transporte ocorre durante a adição, isto corresponde a uma fusão de duas árvores binomiais durante a fusão.

Cada árvore tem ordem de, no máximo log n e, portanto, o tempo de execução é O(log n).

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())

        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())

        heap.addTree(tree)
        heap.next(); p.next(); q.next()

Inserção

A inserção de um novo elemento em um heap pode ser feito simplesmente pela criação de uma nova heap contendo apenas este elemento e, em seguida, mesclando-o com o heap original. Devido à mesclagem, inserir leva O(log n) em tempo. No entanto, através de uma série de n inserções consecutivas, a inserção tem um tempo amortizado de O(1) (constante).

Encontrar mínimo

Para encontrar o mínimo elemento do heap, encontre o mínimo entre as raízes das árvores binomiais. Isso novamente pode facilmente ser feito em tempo O(log n), pois há apenas O(log n) árvores e, portanto, raízes para examinar.

Usando um ponteiro para a árvore binomial que contém o elemento mínimo, o tempo para esta operação pode ser reduzido para O(1). O ponteiro deve ser atualizado sempre na execução de qualquer operação diferente de Encontrar o mínimo. Isso pode ser feito em O(log n) sem aumentar o tempo de execução de qualquer operação.

Excluir mínimo

Para excluir o mínimo elemento do heap, primeiro encontre este elemento, remova-o de sua árvore binomial, e obtenha uma lista de suas subárvores. Em seguida, transforme esta lista de subárvores em uma heap binomial separada, reordenando-as da menor para a maior ordem. Em seguida, mescle esse heap com o heap original. Uma vez que cada raiz tem no máximo log n filhos, criar esta nova heap é O(log n). A fusão das heaps é O(log n), de modo que toda a operação de excluir o mínimo é O(log n).

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min.root then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

Diminuir chave

Ao diminuir a chave de um elemento, ele pode se tornar menor do que a chave de seu pai, violando a propriedade de min-heap. Se este for o caso, troque o elemento com seu pai, e, possivelmente também com seus avós, e assim por diante, até que a propriedade de min-heap não seja violada. Cada árvore binomial tem altura de no máximo, log n, de modo que isso leva O(log n) em tempo.

Remoção

Para remover um elemento do heap, diminua a sua chave para o infinito negativo (isto é, um valor menor do que qualquer elemento na heap) e em seguida elimine o valor mínimo na heap.

Resumo dos tempos de execução

Nas seguintes complexidades de tempo^[1] O(f) é um limite assintótico superior e Θ(f) é um limite assintótico estreito (ver Notação Big O). Os nomes das funções assumem que é um min-heap.

Operação	Binária^[1]	Binomial^[1]	Fibonacci^[1]^[2]	Brodal^[3]^[a]
encontrar-min	Θ(1)	Θ(log n)	Θ(1)	Θ(1)
remover-min	Θ(log n)	Θ(log n)	O(log n)^[b]	O(log n)
inserção	O(log n)	Θ(1)^[b]	Θ(1)	Θ(1)
diminuir-chave	Θ(log n)	Θ(log n)	Θ(1)^[b]	Θ(1)
merge	Θ(n)	O(log n)^[c]	Θ(1)	Θ(1)

↑ Brodal e Okasaki descrevem mais tarde uma variante persistente com os mesmos limites, exceto para o diminuir-chave, que não é suportado. Heaps com n elementos podem ser construídas de baixo-para-cima em O(n).^[4]
↑ ^a ^b ^c Tempo amortizado.
↑ n é o tamanho do maior heap.

Aplicações

Ver também

Referências

↑ ^a ^b ^c ^d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill
↑ Fredman, Michael Lawrence; Tarjan, Robert E. «Fibonacci heaps and their uses in improved network optimization algorithms» (PDF). July 1987. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874
↑ Brodal, Gerth S. (1996), «Worst-Case Efficient Priority Queues» (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
↑ Goodrich, Michael T.; Tamassia, Roberto (2004). «7.3.6. Bottom-Up Heap Construction». Data Structures and Algorithms in Java 3rd ed. [S.l.: s.n.] pp. 338–341. ISBN 0-471-46983-1

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill
21. doi:10.1145/359460.359478

Ligações externas

Java applet simulation of binomial heap
Python implementation of binomial heap
Two C implementations of binomial heap (a generic one and one optimized for integer keys)
Haskell implementation of binomial heap
Common Lisp implementation of binomial heap

[brodal-5] Brodal e Okasaki descrevem mais tarde uma variante persistente com os mesmos limites, exceto para o diminuir-chave, que não é suportado. Heaps com n elementos podem ser construídas de baixo-para-cima em O(n).^[4]

[amortized-6] Tempo amortizado.

[merge-7] é o tamanho do maior heap.

[CLRS-1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill

[Fredman_And_Tarjan-2] Fredman, Michael Lawrence; Tarjan, Robert E. «Fibonacci heaps and their uses in improved network optimization algorithms» (PDF). July 1987. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874

[3] Brodal, Gerth S. (1996), «Worst-Case Efficient Priority Queues» (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[4] Goodrich, Michael T.; Tamassia, Roberto (2004). «7.3.6. Bottom-Up Heap Construction». Data Structures and Algorithms in Java 3rd ed. [S.l.: s.n.] pp. 338–341. ISBN 0-471-46983-1

[1]

[2]

[3]

[a]

[b]

[c]

[4]

v d e Estrutura de dados
Tipos	Coleção Container
Abstrato	Vetor associativo Multimap Lista Pilha Fila Deque Fila de prioridade Fila de prioridade duplamente terminada Conjunto Multiset Disjoint-set
Arrays	Bit array Buffer circular Array dinâmico Tabela hash Matriz esparsa
Vinculada	Lista associativa Lista ligada Skiplist Lista ligada XOR
Árvore	Árvore B Árvore binária de busca Árvore AA Árvore AVL Árvore rubro-negra Árvore binária de busca balanceada Árvore splay Heap Heap binária Heap binomial Heap de Fibonacci Árvores R Árvore R* Árvore R+ Árvore R de Hilbert Trie Árvores de Merkle
Grafos	Diagramas de decisão binária Grafos acíclicos dirigidos Autômato finito determinístico acíclico
Lista de estruturas de dados

v d e Árvores (estrutura de dados)
Árvores de busca (conjuntos dinâmicos/vetores associativos)	2-3 2-3-4 AA (a,b) AVL B B+ B* Binária Intervalo Rubro-negra Scapegoat Splay T Treap
Heaps	Binária Binomial Brodal Fibonacci Esquerdista Van Emde Boas
Tries	PATRICIA Sufixo Ternária
Árvores de particionamento de dados espaciais	BK BSP Hilbert R k-d M Métrica Octree Quaternária R R+ R* Segmentos VP
Outras árvores	Fenwick K-ária Merkle Hiperbólica